class Solution:
    def totalNQueens(self, n: int) -> int:
        self.board = [[0 for _ in range(n)] for _ in range(n)]
        self.n = n
        self.result = 0
        self.backtracking(0)
        return self.result

    def isValid(self,col,row):
        # 竖线
        for i in range(col):
            if self.board[i][row]:
                return False
        # 45只需向上
        ncol = col
        nrow = row
        while 0<=ncol<self.n and 0<=nrow<self.n:
            if self.board[ncol][nrow]:
                return False
            ncol -= 1
            nrow += 1
        
        ncol = col
        nrow = row
        while 0<=ncol<self.n and 0<=nrow<self.n:
            if self.board[ncol][nrow]:
                return False
            ncol -= 1
            nrow -= 1
        return True
    
    def backtracking(self,col):
        if col >self.n:
            self.result += 1
            return
        for drow in range(self.n):
            if not self.isValid(col,drow): continue
            self.board[col][drow] = 1
            col += 1

            self.backtracking(col)

            col -= 1
            self.board[col][drow] = 0


        
s = Solution()
s.totalNQueens(4)